/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 九转苍翎
 * Date: 2025/10/27
 * Time: 20:28
 */
public class Solution {
    public int trap(int[] height) {
        int ret = 0;
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];
        //处理左侧最大值数组
        left[0] = height[0];
        for (int i = 1; i < n; i++) {
            left[i] = Math.max(left[i - 1], height[i]);
        }
        //处理右侧最大值数组
        right[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], height[i]);
        }
        //求结果
        for (int i = 1; i < n - 1; i++) {
            ret += Math.min(left[i], right[i]) - height[i];
        }
        return ret;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int trap = solution.trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1});
        System.out.println(trap);
    }
}
